from typing import *


class Solution:

    def minimumBeautifulSubstrings(self, s: str) -> int:
        if s[0] == '0':
            return -1
        def num(s):
            ans = 0
            i = 1
            r = len(s) - 1
            while r >= 0:
                c = s[r]
                if c == '1':
                    ans += i
                i <<= 1
                r -= 1
            return ans

        def p(s):
            if s == 0:
                return 0
            while s != 1 and s % 5 == 0:
                s //= 5
            return s == 1

        def f(s):
            if p(num(s)):
                return 1
            c = 100
            for i in range(len(s) - 1, 0, -1):
                if s[i]!='0':
                    c1, c2 = f(s[0:i]), f(s[i:])
                    if c1 != -1 and c2 != -1:
                        c = min(c, c1 + c2)
            return -1 if c == 100 else c

        return f(s)

class Solution:

    def minimumBeautifulSubstrings(self, s: str) -> int:
        

        return 0

s = Solution()
# print(s.minimumBeautifulSubstrings("1011"))
# print(s.minimumBeautifulSubstrings("111"))

test_case = ["1011",
"111",
"0",
"110111111111101",
"00001111001111"]
ans_case =[2,3,-1,7,-1]
for case,ans in zip(test_case,ans_case):
    print(s.minimumBeautifulSubstrings(case) == ans)
